Minimum Subset Sum Difference (hard)
Problem Statement #
Given a set of positive numbers, partition the set into two subsets with minimum difference between their subset sums.
Example 1: #
Input: {1, 2, 3, 9}
Output: 3
Explanation: We can partition the given set into two subsets where minimum absolute difference
between the sum of numbers is '3'. Following are the two subsets: {1, 2, 3} & {9}.
Example 2: #
Input: {1, 2, 7, 1, 5}
Output: 0
Explanation: We can partition the given set into two subsets where minimum absolute difference
between the sum of number is '0'. Following are the two subsets: {1, 2, 5} & {7, 1}.
Example 3: #
Input: {1, 3, 100, 4}
Output: 92
Explanation: We can partition the given set into two subsets where minimum absolute difference
between the sum of numbers is '92'. Here are the two subsets: {1, 3, 4} & {100}.
Basic Solution #
This problem follows the 0/1 Knapsack pattern and can be converted into a Subset Sum problem.
Let’s assume S1 and S2 are the two desired subsets. A basic brute-force solution could be to try adding each element either in S1 or S2 in order to find the combination that gives the minimum sum difference between the two sets.
So our brute-force algorithm will look like:
Code #
Here is the code for the brute-force solution:
Time and Space complexity #
Because of the two recursive calls, the time complexity of the above algorithm is exponential , where ‘n’ represents the total number. The space complexity is which is used to store the recursion stack.
Top-down Dynamic Programming with Memoization #
We can use memoization to overcome the overlapping sub-problems.
We will be using a two-dimensional array to store the results of the solved sub-problems. We can uniquely identify a sub-problem from ‘currentIndex’ and ‘Sum1’ as ‘Sum2’ will always be the sum of the remaining numbers.
Code #
Here is the code:
Bottom-up Dynamic Programming #
Let’s assume ‘S’ represents the total sum of all the numbers. So, in this problem, we are trying to find a subset whose sum is as close to ‘S/2’ as possible, because if we can partition the given set into two subsets of an equal sum, we get the minimum difference, i.e. zero. This transforms our problem to Subset Sum, where we try to find a subset whose sum is equal to a given number-- ‘S/2’ in our case. If we can’t find such a subset, then we will take the subset which has the sum closest to ‘S/2’. This is easily possible, as we will be calculating all possible sums with every subset.
Essentially, we need to calculate all the possible sums up to ‘S/2’ for all numbers. So how can we populate the array db[TotalNumbers][S/2+1] in the bottom-up fashion?
For every possible sum ‘s’ (where 0 <= s <= S/2), we have two options:
- Exclude the number. In this case, we will see if we can get the sum ‘s’ from the subset excluding this number =>
dp[index-1][s] - Include the number if its value is not more than ‘s’. In this case, we will see if we can find a subset to get the remaining sum =>
dp[index-1][s-num[index]]
If either of the two above scenarios is true, we can find a subset with a sum equal to ‘s’. We should dig into this before we can learn how to find the closest subset.
Let’s draw this visually, with the example input {1, 2, 3, 9}. Since the total sum is ‘15’, we will try to find a subset whose sum is equal to the half of it, i.e. ‘7’.
The above visualization tells us that it is not possible to find a subset whose sum is equal to ‘7’. So what is the closest subset we can find? We can find the subset if we start moving backwards in the last row from the bottom right corner to find the first ‘T’. The first “T” in the diagram above is the sum ‘6’, which means that we can find a subset whose sum is equal to ‘6’. This means the other set will have a sum of ‘9’ and the minimum difference will be ‘3’.
Code #
Here is the code for our bottom-up dynamic programming approach:
Time and Space complexity #
The above solution has the time and space complexity of , where ‘N’ represents total numbers and ‘S’ is the total sum of all the numbers.